package com.chl.sort.other;

/**
 * <pre>
 * 堆排序 - 不稳定
 * 
 * 思想 
 * 		利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
 * 
 * 算法描述
 * 		① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
 * 		② 依次将根节点与待排序序列的最后一个元素交换
 * 		③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
 * 
 * 备注
 * 		一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；
 * 		其左右子结点分别为 (2i + 1)、(2i + 2)
 * </pre>
 * 
 * @author 陈宏亮
 *
 */
public class Sort07Heap {
	static int[] arrs;

	public static void sort(int[] arr) {
		arrs = arr;
		/*
		 * 第一步：将数组堆化 beginIndex = 第一个非叶子节点。 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
		 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
		 */
		int last = arrs.length - 1;
		int beginIndex = (last - 1) >> 1;
		int i;
		for (int t = beginIndex; t >= 0; t--) {
			i = t;
			do {
				i = buildMaxHeap(i, last);
			} while (i >= t);
		}
		/*
		 * 第二步：对堆化数据排序 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
		 * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。 直至未排序的堆长度为 0。
		 */
		int times = last;
		for (int t = 0; t < times; t++) {
			swaps(0, last);
			last--;
			i = 0;
			do {
				i = buildMaxHeap(i, last);
			} while (i >= 0);
		}
	}
	private static int buildMaxHeap(int i, int last) {
		// 左节点
		int l = i * 2 + 1;
		// 右节点
		int r = i * 2 + 2;
		// 存在右节点
		if (r <= last) {
			if (arrs[r] > arrs[l]) {
				if (arrs[r] > arrs[i]) {
					swaps(r, i);
					return r;// 下移指针
				}
			} else if (arrs[l] > arrs[i]) {
				swaps(l, i);
				return l;// 下移指针
			}
		} else if (l <= last && arrs[l] > arrs[i]) {
			swaps(l, i);
			return l; // 下移指针
		}
		
		// 说明没有移动，i位置元素大于孩子节点，上移指针。
		if (i == 0) {
			return -1;
		} else {
			return (i - 1) / 2;
		}
	}

	private static void swaps(int i, int j) {
		int tmp = arrs[j];
		arrs[j] = arrs[i];
		arrs[i] = tmp;
	}

	/**
	 * 堆排序的主要入口方法，共两步。
	 */
	public static void sorts(int[] arr) {
		arrs = arr;
		/*
		 * 第一步：将数组堆化 beginIndex = 第一个非叶子节点。 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
		 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
		 */
		int len = arrs.length - 1;
		int beginIndex = (len - 1) >> 1;
		for (int i = beginIndex; i >= 0; i--) {
			maxHeapify(i, len);
		}
		
		Sort00Demo.print(arrs);

		/*
		 * 第二步：对堆化数据排序 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
		 * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。 直至未排序的堆长度为 0。
		 */
		for (int i = len; i > 0; i--) {
			swaps(0, i);
			maxHeapify(0, i - 1);
		}
	}

	/**
	 * 调整索引为 index 处的数据，使其符合堆的特性。
	 *
	 * @param index 需要堆化处理的数据的索引
	 * @param len   未排序的堆（数组）的长度
	 */
	private static void maxHeapify(int index, int len) {
		int li = (index << 1) + 1; // 左子节点索引
		int ri = li + 1; // 右子节点索引
		int cMax = li; // 子节点值最大索引，默认左子节点。

		if (li > len)
			return; // 左子节点索引超出计算范围，直接返回。
		if (ri <= len && arrs[ri] > arrs[li]) // 先判断左右子节点，哪个较大。
			cMax = ri;
		if (arrs[cMax] > arrs[index]) {
			swaps(cMax, index); // 如果父节点被子节点调换，
			maxHeapify(cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。
		}
	}
}
